package cn.aylog.gragh;

import com.sun.org.apache.xalan.internal.xsltc.runtime.Node;

import java.util.*;

/**
 * 图的创建和遍历
 * 深度优先遍历(dfs)
 * 广度优先遍历(bfs)
 */
public class Graph {
    public static void main(String[] args) {
        // String[] nodes = {"A", "B", "C", "D", "E"};
        // Graph graph = new Graph(5);
        // for (String node : nodes) {
        //     graph.addNode(node);
        // }
        // graph.linkEdge("A","B",1);
        // graph.linkEdge("A","C",1);
        // graph.linkEdge("B","C",1);
        // graph.linkEdge("B","D",1);
        // graph.linkEdge("B","E",1);
        // // graph.show();
        // graph.dfs("A");
        // graph.bfs("A");


        String[] nodes = {"A", "B", "C", "D", "E", "F", "G", "H", "I"};
        Graph graph = new Graph(nodes.length);
        for (String node : nodes) {
            graph.addNode(node);
        }
        graph.linkEdge("A", "B", 1);
        graph.linkEdge("A", "C", 1);
        graph.linkEdge("B", "D", 1);
        graph.linkEdge("C", "D", 1);
        graph.linkEdge("D", "E", 1);
        graph.linkEdge("E", "F", 1);
        graph.linkEdge("F", "G", 1);
        graph.linkEdge("F", "H", 1);
        graph.linkEdge("G", "I", 1);
        graph.linkEdge("H", "I", 1);
        // graph.dfs("A"); // A->B->D->C->E->F->G->I->H->
        // graph.bfs("A"); // A->B->C->D->E->F->G->H->I->
    }

    int[][] map; // 用于保存节点关系
    int edge; // 边的数量
    List<String> nodes = new ArrayList<>();
    boolean[] flags;

    /**
     * @param n 节点数量
     */
    public Graph(int n) {
        map = new int[n][n];
        edge = 0;
        flags = new boolean[n];
    }

    /**
     * 节点增加
     */
    public void addNode(String node) {
        nodes.add(node);
    }

    /**
     * 增加边,描述关系
     */
    public void linkEdge(String node1, String node2, int weight) {
        int row = nodes.indexOf(node1);
        int col = nodes.indexOf(node2);
        setWight(row, col, weight);
    }

    /**
     * 设置节点的边关系
     *
     * @param w 权重, 0 或 1
     */
    private void setWight(int x, int y, int w) {
        map[x][y] = w;
        map[y][x] = w;
        edge++;
    }

    /**
     * 获取当前节点最近的一个可到达的节点
     */
    public int getFirstArrivedNode(String curNode) {
        int curIndex = nodes.indexOf(curNode);
        for (int x = 0; x < nodes.size(); x++) {
            if (map[curIndex][x] > 0 && !flags[x]) {
                return x;
            }
        }
        return -1;
    }

    /**
     * 获取下一个节点
     */
    public int getNextArrivedNode(String curNode) {
        int curIndex = nodes.indexOf(curNode);
        for(int x=0; x<nodes.size(); x++) {
            if(map[x][curIndex] > 0 && !flags[x]) {
                return x;
            }
        }
        return -1;
    }

    /**
     * 深度优先遍历
     */
    public void dfs(String startNode) {
        // 获取起始节点
        System.out.print(startNode + "->");
        flags[nodes.indexOf(startNode)] = true;
        int ret = getFirstArrivedNode(startNode);
        while (ret != -1) {
            dfs(nodes.get(ret));
            ret = getFirstArrivedNode(startNode);
        }
    }

    Deque<String> deque = new ArrayDeque<>();
    /**
     * 广度优先算法
     */
    public void bfs(String startNode) {
        if(!flags[nodes.indexOf(startNode)]) {
            System.out.print(startNode + "->");
            flags[nodes.indexOf(startNode)] = true;
        }
        int ret = getNextArrivedNode(startNode);
        while(ret != -1) {
            String next = nodes.get(ret);
            deque.add(next);
            System.out.print(next + "->");
            flags[nodes.indexOf(next)] = true;
            ret = getNextArrivedNode(startNode);
        }
        if(!deque.isEmpty()) {
            bfs(deque.removeFirst());
        }
    }
    /**
     * 显示连接关系
     */
    public void show() {
        for(int[] row : map) {
            System.out.println(Arrays.toString(row));
        }
    }
}
